Перейти к основному содержимому

3.05. Теория данных

В РАЗРАБОТКЕНЕ ДЛЯ НОВИЧКОВНЕ ОБЯЗАТЕЛЬНО

Разработчику Аналитику Тестировщику
Архитектору Инженеру

Теория данных​

1. Основы теории информатики в части данных​

Теория данных вытекает из более общей теории информации, предложенной Клодом Шенноном, и из теории вычислимости, развитой Алонзо Чёрчем, Алланом Тьюрингом и другими. Однако в контексте информационных систем данные рассматриваются не как энтропийные величины, а как структурированные объекты, подлежащие манипуляции в рамках строго определённых моделей.

Ключевое понятие — данные как представление знаний. Любая система хранения данных предполагает наличие модели, определяющей:

  • какие типы данных допустимы;
  • как данные связаны между собой;
  • как над ними могут быть выполнены операции;
  • как обеспечивается целостность и согласованность.

В теории информатики данные формализуются через понятие реляции (в рамках реляционной модели), графа (в графовых базах), документа (в документ-ориентированных системах) или ключа-значения (в key-value хранилищах). Эти модели не являются взаимоисключающими — они отражают различные уровни абстракции и подходы к организации информации в зависимости от требований приложения.

Наиболее строго и формально развита реляционная модель данных, предложенная Эдгаром Коддом в 1970 году. Она базируется на теории множеств и логике предикатов первого порядка и до сих пор остаётся основой для большинства промышленных СУБД.

2. Как работает база данных и СУБД на самом низшем уровне​

Система управления базами данных (СУБД) — это программный комплекс, предоставляющий интерфейс для хранения, извлечения, модификации и управления данными с гарантией их целостности, безопасности и производительности. На самом низком уровне СУБД — это набор алгоритмов и структур данных, которые взаимодействуют с операционной системой и, через неё, с аппаратными ресурсами вычислительной машины.

Основные компоненты СУБД на уровне реализации:

  • Менеджер буферов (Buffer Manager) — отвечает за перемещение данных между оперативной памятью и диском.
  • Менеджер дискового пространства (Storage Manager) — управляет физическим расположением данных на диске, включая файлы, страницы и блоки.
  • Менеджер транзакций (Transaction Manager) — обеспечивает ACID-свойства (атомарность, согласованность, изолированность, долговечность).
  • Менеджер выполнения запросов (Query Execution Engine) — преобразует логические операции (например, SELECT) в последовательность физических действий над данными.
  • Оптимизатор запросов (Query Optimizer) — выбирает наиболее эффективный план выполнения запроса на основе статистики и стоимости операций.

На аппаратном уровне данные хранятся в виде последовательностей байтов на энергонезависимом носителе — традиционно на жёстком диске (HDD) или твердотельном накопителе (SSD). СУБД не работает напрямую с оборудованием, а использует системные вызовы операционной системы (read, write, mmap и др.) для доступа к файлам базы данных.

3. Где хранятся данные (на диске)​

Физическое хранение данных в реляционной СУБД обычно организовано по принципу страничной структуры. База данных представляет собой один или несколько файлов, разделённых на фиксированные блоки — страницы (pages), типичный размер которых составляет 4 КБ, 8 КБ или 16 КБ, в зависимости от СУБД (например, PostgreSQL использует 8 КБ, Microsoft SQL Server — 8 КБ по умолчанию).

Каждая страница содержит:

  • заголовок (метаданные: тип страницы, идентификатор отношения, контрольные суммы и т.п.);
  • тело — фрагменты записей (tuples или rows);
  • иногда — слот-массив, указывающий смещения записей внутри страницы.

Записи (rows) не обязательно хранятся последовательно — они могут фрагментироваться, особенно при обновлении переменной длины. Для поддержки целостности и быстрого доступа используется индексная структура, чаще всего — сбалансированное дерево (B+ дерево), которое также хранится на диске в виде страниц.

Важно понимать: диск — это иерархический, последовательный по природе носитель. Даже в SSD, где отсутствует механический seek, эффективность чтения/записи зависит от выравнивания блоков и внутренней архитектуры контроллера NAND-памяти. Поэтому СУБД стремятся минимизировать количество случайных обращений и максимизировать локальность данных.

4. Как СУБД работает с диском​

Когда приходит SQL-запрос, например SELECT * FROM users WHERE id = 100, СУБД не читает всю таблицу с диска целиком. Вместо этого она:

  1. Анализирует запрос и строит его логическое представление (предикаты, соединения и т.п.).
  2. Оптимизатор выбирает план выполнения — например, использовать индекс по полю id.
  3. Менеджер выполнения инициирует чтение нужных страниц с диска через менеджер буферов.
  4. Менеджер буферов проверяет, есть ли запрашиваемая страница в оперативной памяти (в буферном пуле). Если нет — выполняется системный вызов для чтения с диска.
  5. Прочитанная страница кэшируется в памяти, чтобы последующие запросы к тем же данным не требовали повторного обращения к диску.

Таким образом, работа с диском происходит лениво и выборочно: только те страницы, которые действительно нужны для выполнения запроса, загружаются в память. Это критически важно, поскольку объём данных на диске может значительно превышать объём оперативной памяти.

СУБД также использует запись журналов (Write-Ahead Logging, WAL): перед тем как изменить данные на диске, СУБД записывает изменения в специальный лог (журнал транзакций), что позволяет восстановить согласованное состояние после сбоя.

5. Почему базы данных предпочтительнее хранения в ОЗУ​

Хранение данных исключительно в оперативной памяти (in-memory) возможно и используется в специализированных системах (например, Redis, MemSQL). Однако классические СУБД с дисковым хранением обладают рядом фундаментальных преимуществ:

  • Долговечность (Durability): данные сохраняются после выключения питания или аварийного завершения работы. ОЗУ — энергозависимый ресурс.
  • Масштабируемость по объёму: объём диска измеряется терабайтами и петабайтами, тогда как ОЗУ ограничено физическими и экономическими рамками.
  • Контроль целостности: СУБД реализует сложные механизмы (ограничения, внешние ключи, триггеры, ACID), которые невозможно или нецелесообразно воспроизводить вручную в пользовательском коде.
  • Конкуренция и изоляция: СУБД управляет параллельным доступом множества клиентов к данным, обеспечивая корректность через механизмы блокировок, MVCC (многоверсионного управления конкурентным доступом) и т.д.
  • Оптимизированная работа с носителем: СУБД знают структуру данных и могут эффективно использовать индексы, кластеризацию, сжатие и предвыборку (prefetching), что недоступно при простом хранении в памяти.

In-memory хранилища — это частный случай, оправданный при строгих требованиях к задержке, но они не заменяют дисковые СУБД в общем случае.

6. Реляционная алгебра и реляционное исчисление​

Реляционная модель данных, предложенная Эдгаром Коддом, покоится на двух формальных основаниях: реляционной алгебре и реляционном исчислении. Эти две системы не дублируют друг друга, а скорее дополняют: первая ориентирована на как вычислять результат, вторая — на что должно быть в результате.

Реляционная алгебра — это процедурный формализм. Она состоит из набора операторов, которые принимают одно или несколько отношений (таблиц) и возвращают новое отношение. Основные операторы включают:

  • Выборку (selection) — фильтрация строк по условию;
  • Проекцию (projection) — выбор подмножества столбцов;
  • Декартово произведение — комбинирование всех строк двух отношений;
  • Соединение (join) — комбинирование строк с учётом условия соответствия;
  • Объединение, пересечение и разность — теоретико-множественные операции над совместимыми по структуре отношениями;
  • Переименование атрибутов — изменение имён столбцов без изменения содержания.

Каждая операция алгебры строго определена и всегда возвращает корректное отношение. Это позволяет строить планы выполнения запросов как последовательности этих операций. Именно реляционная алгебра лежит в основе внутреннего представления SQL-запросов в большинстве СУБД: парсер SQL преобразует запрос в древовидную структуру, соответствующую выражению реляционной алгебры, которое затем оптимизируется и исполняется.

Реляционное исчисление, в свою очередь, основано на логике предикатов первого порядка. Оно позволяет формулировать запросы в декларативной форме: указывается, какие кортежи должны присутствовать в результате, через логические условия, которым они должны удовлетворять. Например, «найти все строки, для которых существует запись в другой таблице с таким же идентификатором». В отличие от алгебры, здесь не задаётся последовательность шагов — только условие результата.

Ключевой теоретический результат — эквивалентность реляционной алгебры и реляционного исчисления в выразительной силе. Это означает, что любой запрос, выразимый в одной системе, может быть выражен и в другой. Более того, Кодд ввёл понятие реляционной полноты: СУБД считается реляционно полной, если она способна реализовать все операции реляционной алгебры. SQL, несмотря на некоторые отклонения от чистой теории (например, допускает дубликаты строк и отсутствие полной поддержки всех свойств отношений), в своей основе соответствует этому требованию.

Эти формальные основы обеспечивают предсказуемость и корректность обработки данных. Пользователь описывает что ему нужно, а СУБД берёт на себя задачу как это получить, используя мощный аппарат оптимизации на основе алгебраических преобразований и статистики данных.

7. Как вычисляются связи на низком уровне​

Термин «связи» в контексте баз данных чаще всего относится к внешним ключам (foreign keys) — ограничениям целостности, устанавливающим, что значение в одном столбце (или наборе столбцов) одной таблицы должно соответствовать значению первичного ключа в другой таблице.

На логическом уровне это выглядит как декларативное правило: «значение столбца user_id в таблице orders должно существовать в столбце id таблицы `users». Однако на физическом уровне реализация этого правила требует конкретных механизмов.

Проверка внешнего ключа выполняется СУБД в момент модификации данных:

  • При вставке строки в дочернюю таблицу (orders) СУБД ищет соответствующую запись в родительской таблице (users). Это поиск по индексу первичного ключа — операция, в большинстве случаев логарифмическая по времени.
  • При удалении или обновлении строки в родительской таблице СУБД проверяет, ссылаются ли на неё какие-либо строки в дочерних таблицах. В зависимости от политики (например, CASCADE, RESTRICT, SET NULL) могут быть выполнены дополнительные действия.

Важно: сами связи не хранятся как отдельные объекты на диске. Нет «ссылок» в том смысле, в каком они существуют в памяти (например, указатели). Связь — это логическое ограничение, реализуемое через:

  • наличие индексов по столбцам внешнего и первичного ключей (для эффективного поиска);
  • выполнение проверок при операциях изменения данных;
  • поддержание согласованности при восстановлении после сбоев (через WAL-журналы).

При выполнении операции соединения (JOIN) СУБД физически комбинирует строки из двух таблиц, сопоставляя значения в соответствующих столбцах. Существует несколько алгоритмов соединения:

  • Вложенные циклы (nested loops) — для каждой строки из левой таблицы просматриваются все строки правой;
  • Соединение по хешу (hash join) — строится хеш-таблица по одной таблице, затем вторая таблица сканируется и сверяется по хешу;
  • Сортировка и слияние (sort-merge join) — обе таблицы сортируются по ключу соединения, затем выполняется линейное слияние.

Выбор алгоритма зависит от объёма данных, наличия индексов, доступной памяти и статистики распределения значений. Все эти алгоритмы оперируют страницами данных, загружаемыми в буферный пул, и стремятся минимизировать количество операций ввода-вывода.

Таким образом, связи в реляционной модели — это не физические указатели, а логические зависимости, поддерживаемые через индексы, алгоритмы соединения и механизмы контроля целостности, реализованные на уровне СУБД.